#include "headfiles.h"

using namespace std;

bool findMissingNum(const char *file_name, unsigned int &num) {
    if (file_name == NULL) {
        cout << "File name is NULL!" << endl;
        return false;
    }

    unsigned int *blocks;
    size_t block_num = 1 << 12;
    blocks = (unsigned int *)malloc(sizeof(unsigned int) * block_num);
    if (blocks == NULL) {
        cout << "Allocate block buffer error!" << endl;
        return false;
    }

    memset(blocks, 0, sizeof(unsigned int) * block_num);

    unsigned char *vec_bit;
    size_t vec_size = 1 << 29;
    
    // Each byte contains 8 bits
    vec_size = vec_size / block_num;
    vec_bit = (unsigned char *) malloc(sizeof(unsigned char) * vec_size);
    memset(vec_bit, 0, sizeof(unsigned char) * vec_size);

    // Open the file
    fstream fs;
    fs.open(file_name, fstream::in);
    if (!fs.is_open()) {
        cout << "File " << file_name << " open error!" << endl;
        return false;
    }

    string str;
    while (fs >> str) {
        if (str.empty()) {
            break;
        }

        unsigned long tmp_num = strtoul(str.c_str(), NULL, 10);

        // Numbers with the same high 16 bits are in the same block
        tmp_num = tmp_num >> 20;
        ++blocks[tmp_num];
    }

    size_t i;
    size_t index;
    for (i = 0; i < block_num; i++) {
        if (blocks[i] < vec_size * 8) {
            index = i;
            break;
        }
    }

    if (i == block_num) {
        cout << "All distinct numbers are available!" << endl;
        return false;
    }

    // Index is the block in which at least one number is missed

    // See the point to the beginning of the file stream and
    // scan the file again
    fs.seekg(ios_base::beg);
    while (fs >> str) {
        if (str.empty()) {
            break;
        }

        unsigned long tmp_num = strtoul(str.c_str(), NULL, 10);
        size_t block_index = tmp_num >> 20;
        // This num belongs to the block containing missing number
        if (block_index == index) {
            size_t bit_index = tmp_num & 0xFFFFF;
            size_t byte_index = bit_index >> 3;
            size_t byte_internal_index = bit_index & 7;
            unsigned int byte_val = 1 << byte_internal_index;
            vec_bit[byte_index] |= byte_val;
        }
    }
    fs.close();

    for (i = 0; i < vec_size; i++) {
        if (vec_bit[i] < 0xFF) {
            break;
        }
    }

    if (i == vec_size) {
        cout << "No missing number!" << endl;
        return false;
    }

    unsigned int missing_num = i * 8;
    unsigned char byte_val = vec_bit[i];
    // Each bit indicates a number value
    for (i = 0; i < 8; i++) {
        // If a bit is 0, it means that number does not exist
        if ((byte_val & 1) == 0) {
            break;
        }
        byte_val = byte_val >> 1;
    }
    missing_num += i;

    num = missing_num;

    return true;
}


